#pragma once

#include <cassert>
#include <vector>
#include <type_traits>

namespace Transfer
{
    template<typename T>
    class const_array_iterator;

    template<typename T>
    class array_iterator;

    template<typename T>
    class base_array_iterator;

    template<typename T>
    struct _array_op
    {
        static void construct(T* p, const T& val)
        {
            if constexpr(std::is_trivial<T>::value)
                *p = val;
            else
                new(p) T(val);       
        }

        static void construct(T* p, T&& val)
        {
            if constexpr(std::is_trivial<T>::value)
                *p = val;
            else
                new(p) T(val);
        }

        static void destruct(T* p)
        {
            if constexpr(!std::is_trivially_destructible<T>::value)
                p->~T();
        }
    };
    
    /*
    高效环形数组，填满后最后 push 的元素会挤出头部的元素。
    GCC9.0编译器 Linux X64平台测试结果:
    push操作
        比std::deque快 1 倍
        比std::list快 2 倍
        比vector根据数组元素的多少快若干数量级
    随机访问
        不支持
    */
    template<typename T>
    class CycleArray
    {
        struct Item
        {
            T value;
            Item* next;

            void destroy()
            {
                _array_op<T>::destruct(&value);
            }
            void build(const T& v)
            {
                _array_op<T>::construct(&value, v);
            }

            void build(T&& v)
            {
                _array_op<T>::construct(&value, v);
            }
        };
        Item* _elements;
        Item* _front;
        Item* _end;
        ptrdiff_t _capacity;
        ptrdiff_t _count;
    public:
        typedef const_array_iterator<T> const_iterator;
        typedef array_iterator<T> iterator;
    public:
        CycleArray(size_t capacity = 20)
        :_capacity(capacity + 1)
        {
            assert(capacity > 2);
            
            init(capacity);
        }

        ~CycleArray()
        {
            if constexpr(!std::is_trivially_destructible<T>::value)
            {
                while (_front != _end)
                {
                    _front->destroy();
                    _front = _front->next;
                }
            }
            
            delete[] (char*)_elements;
            _elements = nullptr;
            _front = 0;
            _end = 0;
            _capacity = 0;
            _count = 0;
        }

        CycleArray(CycleArray<T>&& other)
        {
            _capacity = other._capacity;
            _count = other._count;
            _elements = other._elements;
            _front = other._front;
            _end = other._end;

            other._count = 0;
            other._elements = nullptr;
            other._capacity = 0;
            other._front = 0;
            other._end = 0;
        }

        CycleArray(const CycleArray<T>& other)
        {
            CopyFrom(other);
        }

        const CycleArray& operator=(const CycleArray<T>& other)
        {
            if (this != &other)
            {
                this->~CycleArray();
                CopyFrom(other);
            }
            return *this;
        }

        void push(const T& element)
        {
            _end->build(element);
            _end = _end->next;
            if (_end == _front)
            {
                _front->destroy();
                _front = _front->next;
            }
            else
            {
                ++ _count;
            }
        }

        void push(T&& element)
        {
            _end->build(element);
            _end = _end->next;
            if (_end == _front)
            {
                _front->destroy();
                _front = _front->next;
            }
            else
            {
                ++ _count;
            }
        }

        size_t size() const
        {
            return _count;
        }

        T& operator[](ptrdiff_t i)
        {
            auto index = (_front - _elements) + i;
            if (index>_capacity) index -= _capacity;
            return _elements[index].value;
        }

        const T& operator[](ptrdiff_t i) const
        {
            auto index = (_front - _elements) + i;
            if (index>_capacity) index -= _capacity;
            return _elements[index].value;
        }

        const T& front() const
        {
            return _elements[_front];
        }

        T& front()
        {
            return _elements[_front];
        }

        const T& back() const
        {
            return this->operator[](_count - 1);
        }

        T& back()
        {
            return this->operator[](_count - 1);
        }

        std::vector<T> to_vector() const
        {
            std::vector<T> v;
            for (auto& i : *this)
            {
                v.push_back(i);
            }
            return v;
        }
    public:
        const_iterator begin() const;
        const_iterator end() const;
        iterator begin();
        iterator end();
    private:
        friend class base_array_iterator<T>;
    private:
        void CopyFrom(const CycleArray<T>& other)
        {
            init(other._capacity - 1);
            auto pOther = other._front;
            while (_count < other._count)
            {
                _array_op<T>::construct(&_end->value, pOther->value);
                ++_count;
                ++_end;
                pOther = pOther->next;
            }
        } 

        void init(size_t capacity)
        {
            _elements = (Item*)new char[sizeof(Item) * (capacity + 1)];
            for (size_t i=0; i<capacity; ++i)
            {
                _elements[i].next = &_elements[i+1];
            }
            _elements[capacity].next = _elements;
            _front = _elements;
            _end = _front;
            _count = 0;
            _capacity = capacity + 1;
        }
    };

    template<typename T>
    class base_array_iterator
    {
        typename CycleArray<T>::Item* _pos;
    public:
        base_array_iterator(typename CycleArray<T>::Item* pos)
        : _pos(pos)
        {
        }

        base_array_iterator() : _pos(nullptr)
        {

        }

        base_array_iterator<T> operator++(int)
        {
            auto old = base_array_iterator(*this);
            _pos = _pos->next;
            return old;
        }

        base_array_iterator<T>& operator++()
        {
            _pos = _pos->next;
            return *this;
        }

        const T& operator*() const
        {
            return _pos->value;
        }

        T& operator*()
        {
            return _pos->value;
        }

        const T* operator->() const
        {
            return &_pos->value;
        }

        T* operator->()
        {
            return &_pos->value;
        }

        bool equalsTo(const base_array_iterator<T>& iterB) const
        {
            return this->_pos == iterB._pos;
        }
    };

    template<typename T>
    class const_array_iterator
    {
        base_array_iterator<T> _base_iterator;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef ptrdiff_t difference_type;
        typedef std::input_iterator_tag iterator_category;
    public:
        const_array_iterator()
        {
        }

        const_array_iterator(const base_array_iterator<T>& iter)
        :_base_iterator(iter)
        {

        }

        const_array_iterator<T> operator++(int)
        {
            auto old = const_array_iterator(_base_iterator);
            ++_base_iterator;
            return old;
        }

        const_array_iterator<T>& operator++()
        {
            ++_base_iterator;
            return *this;
        }

        const T& operator*() const
        {
            return *_base_iterator;
        }

        const T* operator->() const
        {
            return _base_iterator.operator->();
        }

        bool equalsTo(const const_array_iterator<T>& iterB) const
        {
            return this->_base_iterator.equalsTo(iterB._base_iterator);
        }
    };

    template<typename T>
    bool operator == (
            const const_array_iterator<T>& iterA,
            const const_array_iterator<T>& iterB)
    {
        return iterA.equalsTo(iterB);
    }

    template<typename T>
    bool operator != (
            const const_array_iterator<T>& iterA,
            const const_array_iterator<T>& iterB)
    {
        return !iterA.equalsTo(iterB);
    }

    template<typename T>
    class array_iterator
    {
        base_array_iterator<T> _base_iterator;
    public:
        typedef T value_type;
        typedef T& reference;
        typedef T* pointer;
        typedef ptrdiff_t difference_type;
        typedef std::forward_iterator_tag iterator_category;
    public:
        array_iterator()
        {

        }

        array_iterator(const base_array_iterator<T>& iter)
        : _base_iterator(iter)
        {

        }

        array_iterator<T> operator++(int)
        {
            auto old = array_iterator(_base_iterator);
            ++_base_iterator;
            return old;
        }

        array_iterator<T>& operator++()
        {
            ++_base_iterator;
            return *this;
        }

        const T& operator*() const
        {
            return *_base_iterator;
        }

        T& operator*()
        {
            return *_base_iterator;
        }

        const T* operator->() const
        {
            return _base_iterator.operator->();
        }

        T* operator->()
        {
            return _base_iterator.operator->();
        }

        bool equalsTo(const array_iterator<T>& iterB) const
        {
            return this->_base_iterator.equalsTo(iterB._base_iterator);
        }
    };

    template<typename T>
    bool operator == (
            const array_iterator<T>& iterA,
            const array_iterator<T>& iterB)
    {
        return iterA.equalsTo(iterB);
    }

    template<typename T>
    bool operator != (
            const array_iterator<T>& iterA,
            const array_iterator<T>& iterB)
    {
        return !iterA.equalsTo(iterB);
    }

    template<typename T>
    typename CycleArray<T>::const_iterator
    CycleArray<T>::begin() const
    {
        return const_array_iterator<T>(
            base_array_iterator<T>(const_cast<CycleArray<T>*>(this)->_front));
    }

    template<typename T>
    typename CycleArray<T>::const_iterator
    CycleArray<T>::end() const
    {
        return const_array_iterator<T>(
            base_array_iterator<T>(const_cast<CycleArray<T>*>(this)->_end));
    }

    template<typename T>
    typename CycleArray<T>::iterator
    CycleArray<T>::begin()
    {
        return array_iterator<T>(
            base_array_iterator<T>(this->_front));
    }

    template<typename T>
    typename CycleArray<T>::iterator
    CycleArray<T>::end()
    {
        return array_iterator<T>(
            base_array_iterator<T>(this->_end));
    }
}
